package com.zhugang.week13.tree;

/**
 * @program algorithms
 * @description: isBalanced
 * @author: chanzhugang
 * @create: 2022/12/30 10:20
 */
public class IsBalanced {

    /**
     * 剑指offer 55-II 平衡二叉树
     * https://leetcode.cn/problems/ping-heng-er-cha-shu-lcof/
     *
     * @param root
     * @return
     */
    private boolean balanced = true;

    public boolean isBalanced(TreeNode root) {
        /**
         * 变相通过计算左右子树的高度差>1，判断是否是平衡二叉树
         * 总结：返回值并非要求解的值；要求解的值放在全局变量中；
         */
        height(root);
        return balanced;
    }

    private int height(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (!balanced) {
            // 剪枝，提取终止
            return 0;
        }
        int leftH = height(root.left);
        int rightH = height(root.right);
        if (Math.abs(leftH - rightH) > 1) {
            // 高度差 > 1,不是平衡二叉树
            balanced = false;
        }
        return Math.max(leftH, rightH) + 1;
    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }
}